// https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/

/*
给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。

在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

输入：nums = [1,10,2,9]  22 4 - 3+6+2+5  5 - 4+5+3+4 6 - 5+4+4+3 7 - 6+3+5+2 2 - 1+8+0+7  1 - 0+9+1+8 
输出：16


 nums = [1,10,3,7] 3 - 2+7+0+4  4 - 3+6+1+3 5 - 4+5+2+2
*/
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


class Solution {
public:
    int minMoves2(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int mid = nums.size() / 2;
		
		int midV = *(nums.begin() + mid);
		int sum = 0;
		for(auto v : nums){
			sum += abs(v-midV);
		}
		return sum;
    }
};


int main(){
	Solution so;
	vector<int> head = {1,10,2,9};
	int num =so.minMoves2(head);
	cout << num << endl;
	return 0;
}